package exhaustion;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * 穷举所有子集
 */
public class ExhaustionSubSet {

    public static void main(String[] args) {

        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);

        System.out.println("递归方式");
        printAllSubSet(list, new ArrayList<>(), 0);

        System.out.println("栈迭代方式");
        printAllSubSet2(list);
    }

    /**
     * 打印所有子集(递归方式)
     *
     * @param list
     * @param subList
     * @param index
     */
    private static void printAllSubSet(List<Integer> list, List<Integer> subList, int index) {
        if (index >= list.size()) {
            System.out.println(subList);
            return;
        }

        //不添加当前元素
        printAllSubSet(list, subList, index + 1);

        //添加当前元素
        ArrayList<Integer> newSubSet = new ArrayList<>(subList);
        newSubSet.add(list.get(index));
        printAllSubSet(list, newSubSet, index + 1);
    }

    /**
     * 打印所有子集(栈方式)
     *
     * @param list
     */
    private static void printAllSubSet2(List<Integer> list) {
        LinkedList<Node> stack = new LinkedList<>();
        stack.addLast(new Node(Collections.emptyList(), 0));
        while (!stack.isEmpty()) {
            Node node = stack.removeLast();
            if (node.index == list.size()) {
                System.out.println(node.list);
            } else {
                stack.add(new Node(node.list, node.index + 1));

                ArrayList<Integer> newList = new ArrayList<>(node.list.size() + 1);
                newList.addAll(node.list);
                newList.add(list.get(node.index));
                stack.addLast(new Node(newList, node.index + 1));
            }
        }
    }

    public static class Node {
        private List<Integer> list;
        private int index;

        public Node(List<Integer> list, int index) {
            this.list = list;
            this.index = index;
        }
    }
}
